A progressive mesh (PM) representation encodes an arbitrary mesh as a simple base mesh M0 and a sequence of n refinement operations called vertex splits. The PM defines an array {M0 . . . Mn} of level-of-detail (LOD) approximations, and supports geomorphs and progressive transmission. Unlike multiresolution frameworks based on subdivision, the meshes in a PM have irregular connectivities that can accurately model sharp features (e.g., creases and corners) at all scales.
One challenge in the PM framework is handling texture maps. Hardware rasterization features, including bump maps, normal maps, and multitexturing, allow fine detail to be captured in texture images parametrized over the mesh. Processes that implicate sources for textures include sampling detailed scanned meshes, evaluating solid textures, ray tracing, and 3D painting. In this regard, there are various problems associated with parametrizing texture images over all meshes in a PM sequence.
A single unfolding of an arbitrary mesh onto a texture image may create regions of high distortion, so generally a mesh must be partitioned into a set of charts. Each chart is parametrized by a region of a texture domain, and these parametrizations collectively form an atlas, an exemplary one of which is illustrated in FIG. 9C. For instance, several schemes simplify a mesh and then construct a texture image chart over each simplified face by sampling attributes, e.g., normals, from the original mesh.
For a PM, one might consider re-using chart images defined on faces of M0 for all meshes M1 . . . Mn. However, the problem is that a PM is generally not chart-compliant, in that its vertex splits can change the chart topology when applied indiscriminately near chart boundaries, thereby forcing parametric discontinuities. For example, the vertex split shown in FIG. 1B changes the adjacency of the three colored charts of FIG. 1A, resulting in the discontinuous texture. Fortunately, it is possible to construct a single atlas parametrization for the entire PM sequence. Chart-compliance can be obtained by first defining the charts on the original mesh, and then constraining a simplification sequence to comply with those chart boundaries, as described by Cohen, Olano and Manocha.
With respect to mesh partitioning, there have been several previous techniques that have proposed methods for parametrizing meshes by partitioning into charts. Krishnamurthy and Levoy describe an interactive system in which the user manually lays out chart boundaries by tracing curves. Maillot et al. partition mesh faces according to a bucketing of face normals. Eck et al. use a Voronoi-based partition. These last two algorithms make little effort to adapt charts to surface geometry, so the chart boundaries can hinder simplification, leading to poor LOD approximations.
The techniques of Lee et al. (“MAPS”) and Guskov et al. (“Normal Meshes”) map edges of the simplified base domain back to the original mesh. While the resulting charts adapt to surface geometry, their boundaries cut across faces of original mesh, requiring addition of new vertices and faces. For the applications described in MAPS and Normal Meshes, these additional vertices are only temporary, because the mesh geometry is subsequently resampled. However, the techniques of MAPS and Normal Meshes are not suited to generating a PM from a user-specified mesh, whose connectivity is often carefully optimized, because the imposition of new vertices is a drawback to such an application.
With respect to chart parametrization, several schemes have been proposed to flatten surface regions to establish a parametrization. These schemes typically obtain the parametrization by minimizing an objective functional. The main distinction between the functionals is how they measure the distance of the parametrization from an isometry, which is a mapping preserving lengths and angles.
Maillot et al. base their metric on edge springs of nonzero rest length, where rest length corresponds to edge length on the surface. To ensure that the parametrization is 1-to-1, i.e., to avoid parametric “buckling,” also called “face flipping,” they add an area-preservation term to the metric. However, a downside to the technique of Maillot et al. is that when the texture domain boundary is fixed, it is unclear how edge rest-lengths should be scaled. Another downside is that the weighting between the edge springs and the area-preservation term must be adjusted to produce an embedding.
Eck et al. propose the harmonic map, which weights edge springs non-uniformly. The weights can sometimes be negative, in which case an embedding is not guaranteed. Floater proposes a similar scheme with a different edge-spring weighting that guarantees embedding for convex boundaries. For either method, the parametrization can be found by solving a linear system.
Lévy and Mallet combine orthogonality and isoparametric terms in their metric. To solve the resulting nonlinear optimization, they iteratively fix one texture component, s or t, and solve for the other using a linear optimization. As with Lindstrom and Turk, a term is added, which must be sufficiently weighted to guarantee an embedding.
Hormann and Greiner propose the MIPS parametrization, which roughly attempts to preserve the ratio of singular values over the parametrization. However, the metric disregards absolute stretch scale over the surface, with the result that small domain areas can map to large regions on the surface.
With respect to appearance preserving simplification, Cohen et al. introduce texture deviation as the appropriate measure of geometric accuracy when simplifying textured meshes. The texture deviation between a simplified mesh Mi and the original mesh Mn at a point pi∈Mi is defined as ∥pi-pn∥ where pn is the point on Mn with the same parametric location in the texture domain. Cohen et al. track texture deviation conservatively by storing a bounding error box at each mesh vertex. They demonstrate results on parametric surfaces already organized into charts; however, the techniques of Cohen et al. do not begin with an unparametrized mesh, and then seek to form an atlas parametrization that specifically minimizes texture deviation and stretch over all meshes in a PM.
Thus, it would be desirable to improve upon prior art techniques for providing texture mapping in connection with parametrization schemes. To improve upon prior art techniques, it would be desirable to provide a system that allows all meshes in the PM to share a common texture map. Furthermore, it would be desirable to create domains with straight boundaries between chart corners, unlike, for example, the approaches of Maillot et al., Lévy and Mallet and Hormann and Greiner. It would be still further desirable to provide systems and methods for texture mapping PMs that minimize geometric stretch and texture deviation. It would be still further desirable to substantially balance sampling rates everywhere on the surface by optimizing the geometric stretch of a parametrization scheme. Moreover, it would be advantageous to provide a general solution that begins with an unparametrized mesh, and then forms an atlas parametrization that minimizes texture deviation and stretch over all meshes in a PM.